//Given a non-empty array of integers, every element appears three times except 
//for one, which appears exactly once. Find that single one. 
//
// Note: 
//
// Your algorithm should have a linear runtime complexity. Could you implement i
//t without using extra memory? 
//
// Example 1: 
//
// 
//Input: [2,2,3,2]
//Output: 3
// 
//
// Example 2: 
//
// 
//Input: [0,1,0,1,0,1,99]
//Output: 99 
// Related Topics 位运算 
// 👍 463 👎 0


package editor.cn;
//Java：Single Number II
public class P137SingleNumberIi{
    public static void main(String[] args) {
        Solution solution = new P137SingleNumberIi().new Solution();
        // TO TEST
        System.out.println(solution.singleNumber(new int[]{2, 1, 2, 2,3,3,3}));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int singleNumber(int[] nums) {
        //基本思想：将第偶数次出现的数字放在另一个变量b中，奇数次的数字在变量a异或,那被干掉的就是就是3、5、7次出现的
        //例如：2，2，2
        //a=2,b=0
        //a=2,b=2
        //a=0.b=2
        //如何实现，最开始
        int a = 0, b = 0;
        for (int num : nums) {
            a = (a ^ num) & ~b;
            b = (b ^ num) & ~a;
        }
        return a;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}